/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-23
 * Time: 23:08
 */

public class Solution {
    /**
     *  背包问题
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1;i <= target;i++) {
//             这个循环里面已经考虑到 顺序了
//             比如如何 到达 4, 可以 1 + 3步到达, 也可以 先走 3 步 , 再走 1 步
//             这样同样是 3 和 1 , 但是考虑了先后顺序了, 所以最终的结果就使得
//             相同的数字, 顺序不同的序列被视作不同的组合
            for (int x: nums) {
                if (i >= x) {
                    dp[i] += dp[i - x];
                }
            }
        }
        return dp[target];
    }
}
